{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Smallest Instructions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthSmallestPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 K 条最小指令"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Bob 站在单元格 <code>(0, 0)</code> ，想要前往目的地 <code>destination</code> ：<code>(row, column)</code> 。他只能向 <strong>右</strong> 或向 <strong>下</strong> 走。你可以为 Bob 提供导航 <strong>指令</strong> 来帮助他到达目的地 <code>destination</code> 。</p>\n",
    "\n",
    "<p><strong>指令</strong> 用字符串表示，其中每个字符：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'H'</code> ，意味着水平向右移动</li>\n",
    "\t<li><code>'V'</code> ，意味着竖直向下移动</li>\n",
    "</ul>\n",
    "\n",
    "<p>能够为 Bob 导航到目的地 <code>destination</code> 的指令可以有多种，例如，如果目的地 <code>destination</code> 是 <code>(2, 3)</code>，<code>\"HHHVV\"</code> 和 <code>\"HVHVH\"</code> 都是有效<strong> 指令</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>然而，Bob 很挑剔。因为他的幸运数字是 <code>k</code>，他想要遵循 <strong>按字典序排列后的第 <code>k</code> 条最小指令 </strong>的导航前往目的地 <code>destination</code> 。<code>k</code>  的编号 <strong>从 1 开始</strong> 。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>destination</code> 和一个整数 <code>k</code> ，请你返回可以为<em> </em>Bob<em> </em>提供前往目的地 <code>destination</code> 导航的<strong> 按字典序排列后的第 <code>k</code> 条最小指令 </strong>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/01/ex1.png\" style=\"width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>destination = [2,3], k = 1\n",
    "<strong>输出：</strong>\"HHHVV\"\n",
    "<strong>解释：</strong>能前往 (2, 3) 的所有导航指令 <strong>按字典序排列后</strong> 如下所示：\n",
    "[\"HHHVV\", \"HHVHV\", \"HHVVH\", \"HVHHV\", \"HVHVH\", \"HVVHH\", \"VHHHV\", \"VHHVH\", \"VHVHH\", \"VVHHH\"].\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/01/ex2.png\" style=\"width: 300px; height: 229px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>destination = [2,3], k = 2\n",
    "<strong>输出：</strong>\"HHVHV\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/01/ex3.png\" style=\"width: 300px; height: 229px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>destination = [2,3], k = 3\n",
    "<strong>输出：</strong>\"HHVVH\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>destination.length == 2</code></li>\n",
    "\t<li><code>1 <= row, column <= 15</code></li>\n",
    "\t<li><code>1 <= k <= nCr(row + column, row)</code>，其中 <code>nCr(a, b)</code> 表示组合数，即从 <code>a</code> 个物品中选 <code>b</code> 个物品的不同方案数。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-smallest-instructions](https://leetcode.cn/problems/kth-smallest-instructions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-smallest-instructions](https://leetcode.cn/problems/kth-smallest-instructions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3]\\n1', '[2,3]\\n2', '[2,3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        row, column = destination[0], destination[1]\n",
    "        if row == 0:\n",
    "            return 'H' * column\n",
    "        if column == 0:\n",
    "            return 'V' * row\n",
    "        k1 = math.comb(row + column - 1, column - 1)\n",
    "        if k <= k1:\n",
    "            return 'H' + self.kthSmallestPath([row, column - 1], k)\n",
    "        else:\n",
    "            return 'V' + self.kthSmallestPath([row - 1, column], k - k1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        x = destination[0]\n",
    "        y = destination[1]\n",
    "        n = x + y\n",
    "        ans = ['H'] * n\n",
    "        for i in range(n):\n",
    "            if x > 0:\n",
    "                kk = comb(n - i - 1, x)\n",
    "                if k > kk:\n",
    "                    k -= kk\n",
    "                    ans[i] = 'V'\n",
    "                    x -= 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        vnum, hnum = destination\n",
    "        res = \"\"\n",
    "        for num in range(vnum + hnum, 0, -1):\n",
    "            what = comb(num-1, vnum)\n",
    "            if k <= what:\n",
    "                res += \"H\"\n",
    "                num -= 1\n",
    "                hnum -= 1\n",
    "            else:\n",
    "                k -= what\n",
    "                res += \"V\"\n",
    "                num -= 1\n",
    "                vnum -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "        ans = list()\n",
    "        for i in range(h + v):\n",
    "            if h > 0:\n",
    "                o = math.comb(h + v - 1, h - 1)\n",
    "                if k > o:\n",
    "                    ans.append(\"V\")\n",
    "                    v -= 1\n",
    "                    k -= o\n",
    "                else:\n",
    "                    ans.append(\"H\")\n",
    "                    h -= 1\n",
    "            else:\n",
    "                ans.append(\"V\")\n",
    "                v -= 1\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        m, n = destination[0] + 1, destination[1] + 1\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[m - 1][n - 1] = 1\n",
    "        # already to right border, only 1 way: just go down\n",
    "        for i in range(m - 1):\n",
    "            dp[i][n - 1] = 1\n",
    "        # already to bottom border, only 1 way: just go right\n",
    "        for j in range(n - 1):\n",
    "            dp[m - 1][j] = 1\n",
    "        \n",
    "        # get all ways count start from point: [i, j]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[i][j] = dp[i][j + 1] + dp[i + 1][j]\n",
    "        \n",
    "        ans = ''\n",
    "        i = j = 0\n",
    "        while j < n - 1 and i < m - 1:\n",
    "            if dp[i][j + 1] >= k: # the kth way is in the go right direction\n",
    "                ans += 'H'\n",
    "                j += 1\n",
    "            else: # the kth way is in the go down direction\n",
    "                ans += 'V'\n",
    "                k -= dp[i][j + 1]\n",
    "                i += 1\n",
    "        # add left path str\n",
    "        ans += 'H' * (n - 1 - j)\n",
    "        ans += 'V' * (m - 1 - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        row, column = destination[0]+1 ,destination[1]+1\n",
    "        dp = [[0]*column for _ in range(row)]\n",
    "        dp[row-1][column-1] = 1\n",
    "        for i in range(row-1):\n",
    "            dp[i][column-1] = 1\n",
    "        for i in range(column-1):\n",
    "            dp[row-1][i] = 1\n",
    "        for i in range(row-2,-1,-1):\n",
    "            for j in range(column-2,-1,-1):\n",
    "                dp[i][j] = dp[i+1][j] + dp[i][j+1]\n",
    "        res = ''\n",
    "        i = j = 0\n",
    "        while i<row-1 and j<column-1:\n",
    "            if dp[i][j+1] >=k:\n",
    "                res += 'H'\n",
    "                j += 1\n",
    "            else:\n",
    "                res +='V'\n",
    "                k -= dp[i][j+1]\n",
    "                i += 1\n",
    "        res += 'H'*(column-1-j)\n",
    "        res += 'V'*(row-1-i)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        N = 31\n",
    "        C = [[0] * N for _ in range(N)]\n",
    "\n",
    "        for i in range(N):\n",
    "            C[i][i] = C[i][0] = 1\n",
    "            for j in range(0, i, 1):\n",
    "                C[i][j] = C[i - 1][j - 1] + C[i - 1][j]\n",
    "        \n",
    "        v, h = destination\n",
    "        res = []\n",
    "        for i in range(v + h):\n",
    "            if k > C[h + v - 1][v]:\n",
    "                res.append('V')\n",
    "                k -= C[h + v - 1][v]\n",
    "                v -= 1\n",
    "            else:\n",
    "                res.append('H')\n",
    "                h -= 1\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "        ans = ''\n",
    "        for i in range(v + h):\n",
    "            if h > 0:\n",
    "                o = comb(h + v - 1, h - 1)\n",
    "                if k > o:\n",
    "                    ans += 'V'\n",
    "                    v -= 1\n",
    "                    k -= o\n",
    "                else: \n",
    "                    ans += 'H'\n",
    "                    h -= 1\n",
    "            else:\n",
    "                ans += 'V'\n",
    "                v -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        c = [[1 for _ in range(i+1)] for i in range(31)]\n",
    "        for i in range(1, 31):\n",
    "            for j in range(1, i):\n",
    "                c[i][j] = c[i-1][j] + c[i-1][j-1]\n",
    "        self.c = c\n",
    "\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "        if h == 0:\n",
    "            return \"V\"*v\n",
    "        if v == 0:\n",
    "            return \"H\"*h\n",
    "        total = h + v\n",
    "        #print(total, h)\n",
    "        if k <= self.c[total-1][h-1]:\n",
    "            return \"H\"+self.kthSmallestPath([v, h-1], k)\n",
    "        else:\n",
    "            return \"V\"+self.kthSmallestPath([v-1, h], k-self.c[total-1][h-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    H V, 组合，全排列，\n",
    "    '''\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        import math\n",
    "        v, h = destination\n",
    "        res = ''\n",
    "        k -= 1\n",
    "        while h and v and k:\n",
    "            now = math.comb(h + v - 1, v)\n",
    "            if now <= k:\n",
    "                k -= now\n",
    "                v -= 1\n",
    "                res += \"V\"\n",
    "            else:\n",
    "                h -= 1\n",
    "                res += \"H\"\n",
    "        res += \"H\" * h + \"V\" * v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        cur_H,cur_V=destination[1],destination[0]\n",
    "        ans=''\n",
    "        for i in range(cur_H+cur_V):\n",
    "            t=math.comb(cur_H+cur_V-1,cur_H-1)\n",
    "            if k<t:\n",
    "                cur_H-=1\n",
    "                ans+='H'\n",
    "            elif k==t:\n",
    "                cur_H-=1\n",
    "                ans+='H'\n",
    "                return ans+'V'*cur_V+'H'*cur_H\n",
    "            elif k==t+1:\n",
    "                cur_V-=1\n",
    "                ans+='V'\n",
    "                return ans+'H'*cur_H+'V'*cur_V\n",
    "            else:\n",
    "                k-=t\n",
    "                ans+='V'\n",
    "                cur_V-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "\n",
    "        v,h = destination\n",
    "        ans = []\n",
    "        def f(v,h, k):\n",
    "            if h == 0 and v == 0:   \n",
    "                return\n",
    "            if h == 0:\n",
    "                ans.append('V')\n",
    "                f(v-1, h, k)\n",
    "            elif v == 0:\n",
    "                ans.append('H')\n",
    "                f(v, h-1, k)\n",
    "            else:\n",
    "                t = comb(h + v - 1, h-1)\n",
    "                if k > t:\n",
    "                    ans.append('V')\n",
    "                    f(v-1, h, k-t)\n",
    "                else:\n",
    "                    ans.append('H')\n",
    "                    f(v, h-1,k)\n",
    "        f(v,h,k)\n",
    "        return ''.join(ans) \n",
    "                \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        h = destination[1]\n",
    "        v = destination[0]\n",
    "        if k == 1:\n",
    "            return 'H'*h+'V'*v\n",
    "        res = ''\n",
    "        while h > 0 and v >0:\n",
    "            num = comb(h+v-1, h-1)\n",
    "            if k >num:\n",
    "                res += 'V'\n",
    "                v -=1\n",
    "                k -= num\n",
    "            else:\n",
    "                res += 'H'\n",
    "                h -= 1\n",
    "        return res+'H'*h+'V'*v\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "\n",
    "        dp = [[0] * h for _ in range(v + h)]\n",
    "        for i in range(h + v):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, h + v):\n",
    "            for j in range(1, h):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]\n",
    "        \n",
    "        res = ''\n",
    "        for i in range(v + h):\n",
    "            if h:\n",
    "                cnt = dp[v + h - 1][h - 1]\n",
    "                if k > cnt:\n",
    "                    res += 'V'\n",
    "                    k -= cnt\n",
    "                    v -= 1\n",
    "                else:\n",
    "                    res += 'H'\n",
    "                    h -= 1\n",
    "            else:\n",
    "                res += 'V'\n",
    "                v -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        row, column = destination[0]+1 ,destination[1]+1\n",
    "        dp = [[0]*column for _ in range(row)]\n",
    "        dp[row-1][column-1] = 1\n",
    "        for i in range(row-1):\n",
    "            dp[i][column-1] = 1\n",
    "        for i in range(column-1):\n",
    "            dp[row-1][i] = 1\n",
    "        for i in range(row-2,-1,-1):\n",
    "            for j in range(column-2,-1,-1):\n",
    "                dp[i][j] = dp[i+1][j] + dp[i][j+1]\n",
    "        res = ''\n",
    "        i = j = 0\n",
    "        while i<row-1 and j<column-1:\n",
    "            if dp[i][j+1] >=k:\n",
    "                res += 'H'\n",
    "                j += 1\n",
    "            else:\n",
    "                res +='V'\n",
    "                k -= dp[i][j+1]\n",
    "                i += 1\n",
    "        res += 'H'*(column-1-j)\n",
    "        res += 'V'*(row-1-i)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "        ans = list()\n",
    "        for i in range(h + v):\n",
    "            if h > 0:\n",
    "                o = math.comb(h + v - 1, h - 1)\n",
    "                if k > o:\n",
    "                    ans.append(\"V\")\n",
    "                    v -= 1\n",
    "                    k -= o\n",
    "                else:\n",
    "                    ans.append(\"H\")\n",
    "                    h -= 1\n",
    "            else:\n",
    "                ans.append(\"V\")\n",
    "                v -= 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        r, c = destination\n",
    "        # r V c H\n",
    "        # c-0 H V     0 H r-1 V\n",
    "        # c-1 H V     1 H r-1 V\n",
    "        # c-2 H V     2 H r-1 V\n",
    "        # ...\n",
    "        # c-c H V     c H r-1 V\n",
    "        def f(n):\n",
    "            if n==0:\n",
    "                return 1\n",
    "            else:\n",
    "                return n*f(n-1)\n",
    "\n",
    "        def nCr(a,b):\n",
    "            return f(a)//f(a-b)//f(b)\n",
    "\n",
    "        def helper(c,r,k):\n",
    "            if c==0: return r*'V'\n",
    "            if r==0: return c*'H'\n",
    "            s=0\n",
    "            for x in range(c+1):\n",
    "                t=nCr(x+r-1,x)\n",
    "                if k<=s+t:\n",
    "                    return 'H'*(c-x)+'V'+helper(x,r-1,k-s)\n",
    "                else:\n",
    "                    s+=t\n",
    "        return helper(c,r,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        test = ['H' for _ in range(sum(destination))]\n",
    "        n = destination[0] + destination[1]\n",
    "        x = destination[0]\n",
    "        while x > 0:\n",
    "            for r in range(x, n + 1):\n",
    "                t = comb(r - 1, x - 1)\n",
    "                if k > t:\n",
    "                    k -= t\n",
    "                else:\n",
    "                    test[r - 1] = 'V'\n",
    "                    x -= 1\n",
    "                    break\n",
    "        return ''.join(test[::-1])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        n, m = destination\n",
    "        total = m + n\n",
    "\n",
    "        def factorial(x):\n",
    "            ans = [1, 1]\n",
    "            for val in range(2, x + 1):\n",
    "                ans.append(ans[-1] * val)\n",
    "            return ans\n",
    "        \n",
    "        pre_factorial = factorial(total)\n",
    "\n",
    "        ans = \"\"\n",
    "\n",
    "        t = 0\n",
    "        while m != 0 and n != 0:\n",
    "            left = pre_factorial[total - t - 1] / pre_factorial[m - 1] / pre_factorial[total - t - m]\n",
    "            if left >= k:\n",
    "                m -= 1\n",
    "                ans += \"H\"\n",
    "            else:\n",
    "                k -= left\n",
    "                n -= 1\n",
    "                ans += \"V\"\n",
    "            t += 1\n",
    "        print(ans)\n",
    "        if m:\n",
    "            ans += \"H\" * m\n",
    "        if n:\n",
    "            ans += \"V\" * n\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        m, n = destination[0] + 1, destination[1] + 1\n",
    "\n",
    "        # 动态规划记录方案数\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[m - 1][n - 1] = 1\n",
    "        for i in range(m - 1):\n",
    "            dp[i][n - 1] = 1\n",
    "        for j in range(n - 1):\n",
    "            dp[m - 1][j] = 1\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[i][j] = dp[i + 1][j] + dp[i][j + 1]\n",
    "\n",
    "        # 模拟移动\n",
    "        ans = \"\"\n",
    "        i = j = 0\n",
    "        while j < n - 1 and i < m - 1:\n",
    "            if dp[i][j + 1] >= k:\n",
    "                ans += \"H\"\n",
    "                j += 1\n",
    "            else:\n",
    "                ans += \"V\"\n",
    "                # 往下走前减去右边的方案数，表示在路径前缀下目标路径的字典排序条数\n",
    "                k -= dp[i][j + 1]\n",
    "                i += 1\n",
    "        ans += \"H\" * (n - 1 - j)\n",
    "        ans += \"V\" * (m - 1 - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    动态规划 + 组合数学\n",
    "    因为是从(0, 0)出发到目的地，且只能向右和向下走，那么目的地坐标对应的行列之和就是V和H一共出现的次数\n",
    "    因为k是按照字典序从小到大排列的，而H的字典序小于V，因此我们要先放H\n",
    "    从高到低位遍历v + h的个数，其实就是最终字符的下标，先放H，假设当前遍历位放了H，那么对于剩下的h - 1个H，和v个V，\n",
    "    一共有C(v + h - 1, h - 1)种组合，注意C(v + h - 1, h - 1) == C(v + h - 1, v)，所以从h还是v的角度看组合\n",
    "    数都是相同的\n",
    "    此时判断如果按字典序数的k个，小于C(v + h - 1, h - 1)，那说明要找的答案就是在当前遍历位放置H的各种组合中，此时\n",
    "    消耗了一个H，继续遍历下一位\n",
    "    如果按照字典序数的k个，大于C(v + h - 1, h - 1)说明，当前遍历位不能放H，只能放V，V消耗一个，C(v + h - 1, h - 1)\n",
    "    种组合直接被消耗掉，继续遍历下一位\n",
    "    '''\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "\n",
    "        '''\n",
    "        人工求组合数dp[i][j]表示C(i, j)，i个元素中选j个元素\n",
    "        '''\n",
    "        dp = [[0] * h for _ in range(v + h)]\n",
    "        for i in range(h + v):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, h + v):\n",
    "            for j in range(1, h):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]\n",
    "        \n",
    "        res = ''\n",
    "        for i in range(v + h):\n",
    "            if h:\n",
    "                cnt = dp[v + h - 1][h - 1]\n",
    "                if k > cnt:\n",
    "                    res += 'V'\n",
    "                    k -= cnt\n",
    "                    v -= 1\n",
    "                else:\n",
    "                    res += 'H'\n",
    "                    h -= 1\n",
    "            else:\n",
    "                res += 'V'\n",
    "                v -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "        ans = []\n",
    "        for i in range(h + v):\n",
    "            if h > 0: # not reach the right border\n",
    "                o = math.comb(h + v - 1, h - 1) # cal the left part count\n",
    "                if k > o: # target is at right part, keep search\n",
    "                    ans.append('V')\n",
    "                    v -= 1\n",
    "                    k -= o\n",
    "                else:\n",
    "                    ans.append('H')\n",
    "                    h -= 1\n",
    "            else: # already reach the right border, complient the whole path\n",
    "                ans.append('V')\n",
    "                v -= 1\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math \n",
    "class Solution:\n",
    "    def kthSmallestPath(self, d: List[int], k: int) -> str:\n",
    "        row, col = d \n",
    "        def dfs(x, y, res):\n",
    "            if x==row:\n",
    "                return ''.join(['H']*(col - y)) \n",
    "            if y==col:\n",
    "                return ''.join(['V']*(row - x)) \n",
    "            if res==1:\n",
    "                return  ''.join(['H']*(col - y))  + ''.join(['V']*(row - x)) \n",
    "            y1 = y+1\n",
    "            tmp = math.comb(col-y1+row-x, col-y1) \n",
    "            if tmp>=res:\n",
    "                return 'H' + dfs(x, y1, res) \n",
    "            else:\n",
    "                return 'V' + dfs(x+1, y, res - tmp) \n",
    "        return dfs(0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        v, h = destination\n",
    "\n",
    "        dp = [[0] * h for _ in range(v + h)]\n",
    "        for i in range(h + v):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1, h + v):\n",
    "            for j in range(1, h):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]\n",
    "        \n",
    "        res = ''\n",
    "        for i in range(v + h):\n",
    "            if h:\n",
    "                if k > dp[v + h - 1][h - 1]:\n",
    "                    res += 'V'\n",
    "                    k -= dp[v + h - 1][h - 1]\n",
    "                    v -= 1\n",
    "                else:\n",
    "                    res += 'H'\n",
    "                    h -= 1\n",
    "            else:\n",
    "                res += 'V'\n",
    "                v -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        def dfs(V: int, H: int, path: List[str], target: int):\n",
    "            nonlocal ans\n",
    "            if V == 0 and H == 0:\n",
    "                ans = \"\".join(path)\n",
    "                return\n",
    "            if V < 0 or H < 0:\n",
    "                return\n",
    "\n",
    "            remains = V + H  - 1\n",
    "\n",
    "            # if we choose H\n",
    "            choose_H = comb(remains, V)\n",
    "            if target <= choose_H and H >= 1:\n",
    "                # print(f\"V: {V}, H: {H}, choose H, target: {target}\")\n",
    "                path.append(\"H\")\n",
    "                dfs(V, H - 1, path, target)\n",
    "            else:\n",
    "                # print(f\"V: {V}, H: {H},choose V, target: {target}\")\n",
    "                target -= choose_H\n",
    "                path.append(\"V\")\n",
    "                dfs(V - 1, H, path, target)\n",
    "            \n",
    "            \n",
    "        V, H = destination\n",
    "        ans = \"\"\n",
    "        dfs(V, H, [], k)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\r\n",
    "class Solution:\r\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\r\n",
    "        res = \"\"\r\n",
    "        v, h = destination\r\n",
    "        n = v + h\r\n",
    "        for i in range(n):\r\n",
    "            if h == 0 or v == 0: break\r\n",
    "            # hcnt numbers of combinations start with \"H\"\r\n",
    "            hcnt = comb(n - i - 1, h - 1)\r\n",
    "            if k <= hcnt:\r\n",
    "                h -= 1\r\n",
    "                res += \"H\"\r\n",
    "            else:\r\n",
    "                k -= hcnt\r\n",
    "                v -= 1\r\n",
    "                res += \"V\"\r\n",
    "\r\n",
    "        while h:\r\n",
    "            res += \"H\"\r\n",
    "            h -= 1\r\n",
    "        while v:\r\n",
    "            res += \"V\"\r\n",
    "            v -= 1\r\n",
    "\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        m, n = destination[0] + 1, destination[1] + 1\n",
    "\n",
    "        # 动态规划记录方案数\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[m - 1][n - 1] = 1\n",
    "        for i in range(m - 1):\n",
    "            dp[i][n - 1] = 1\n",
    "        for j in range(n - 1):\n",
    "            dp[m - 1][j] = 1\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                dp[i][j] = dp[i + 1][j] + dp[i][j + 1]\n",
    "\n",
    "        # 模拟移动\n",
    "        ans = \"\"\n",
    "        i = j = 0\n",
    "        while j < n - 1 and i < m - 1:\n",
    "            if dp[i][j + 1] >= k:\n",
    "                ans += \"H\"\n",
    "                j += 1\n",
    "            else:\n",
    "                ans += \"V\"\n",
    "                # 往下走前减去右边的方案数，表示在路径前缀下目标路径的字典排序条数\n",
    "                k -= dp[i][j + 1]\n",
    "                i += 1\n",
    "        ans += \"H\" * (n - 1 - j)\n",
    "        ans += \"V\" * (m - 1 - i)\n",
    "        return ans\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/kth-smallest-instructions/solutions/1637722/er-xu-cheng-ming-jiu-xu-zui-by-liupengsa-iw0c/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        r, c = destination\n",
    "        # r V c H\n",
    "        # c-0 H V     0 H r-1 V\n",
    "        # c-1 H V     1 H r-1 V\n",
    "        # c-2 H V     2 H r-1 V\n",
    "        # ...\n",
    "        # c-c H V     c H r-1 V\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n==0:\n",
    "                return 1\n",
    "            else:\n",
    "                return n*f(n-1)\n",
    "\n",
    "        @cache\n",
    "        def nCr(a,b):\n",
    "            return f(a)//f(a-b)//f(b)\n",
    "\n",
    "        @cache\n",
    "        def helper(c,r,k):\n",
    "            if c==0: return r*'V'\n",
    "            if r==0: return c*'H'\n",
    "            s=0\n",
    "            for x in range(c+1):\n",
    "                t=nCr(x+r-1,x)\n",
    "                if k<=s+t:\n",
    "                    return 'H'*(c-x)+'V'+helper(x,r-1,k-s)\n",
    "                else:\n",
    "                    s+=t\n",
    "        return helper(c,r,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        r, c = destination\n",
    "        # r V c H\n",
    "        # c-0 H V     0 H r-1 V\n",
    "        # c-1 H V     1 H r-1 V\n",
    "        # c-2 H V     2 H r-1 V\n",
    "        # ...\n",
    "        # c-c H V     c H r-1 V\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n==0:\n",
    "                return 1\n",
    "            else:\n",
    "                return n*f(n-1)\n",
    "\n",
    "        @cache\n",
    "        def nCr(a,b):\n",
    "            return f(a)//f(a-b)//f(b)\n",
    "\n",
    "        @cache\n",
    "        def helper(c,r,k):\n",
    "            if c==0: return r*'V'\n",
    "            if r==0: return c*'H'\n",
    "            s=0\n",
    "            for x in range(c+1):\n",
    "                t=nCr(x+r-1,x)\n",
    "                if k<=s+t:\n",
    "                    return 'H'*(c-x)+'V'+helper(x,r-1,k-s)\n",
    "                else:\n",
    "                    s+=t\n",
    "        return helper(c,r,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "        r, c = destination\n",
    "        # r V c H\n",
    "        # c-0 H V     0 H r-1 V\n",
    "        # c-1 H V     1 H r-1 V\n",
    "        # c-2 H V     2 H r-1 V\n",
    "        # ...\n",
    "        # c-c H V     c H r-1 V\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n==0:\n",
    "                return 1\n",
    "            else:\n",
    "                return n*f(n-1)\n",
    "\n",
    "        @cache\n",
    "        def nCr(a,b):\n",
    "            return f(a)//f(a-b)//f(b)\n",
    "\n",
    "        @cache\n",
    "        def helper(c,r,k):\n",
    "            if c==0: return r*'V'\n",
    "            if r==0: return c*'H'\n",
    "            s=0\n",
    "            for x in range(c+1):\n",
    "                t=nCr(x+r-1,x)\n",
    "                if k<=s+t:\n",
    "                    return 'H'*(c-x)+'V'+helper(x,r-1,k-s)\n",
    "                else:\n",
    "                    s+=t\n",
    "        return helper(c,r,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n",
    "\n",
    "        @cache\n",
    "        def dfs(r, c, pos):\n",
    "            if r == 0:\n",
    "                return 'H' * c\n",
    "            if c == 0:\n",
    "                return 'V' * r\n",
    "            v = math.comb(r + c, r)\n",
    "            v2 = math.comb(r + c - 1, r - 1)\n",
    "            if v - v2 < pos:\n",
    "                return 'V' + dfs(r - 1, c, pos - (v - v2))\n",
    "            else:\n",
    "                return 'H' + dfs(r, c - 1, pos)\n",
    "        return dfs(destination[0], destination[1], k)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
